package Dijkstra算法航线;

import java.util.Scanner;

/**
 * Created by Lee on 2017/4/13.
 */

public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int len = n + 1;
            int g[][] = new int[len][len];
            int x[][] = new int[len][len];
            int y[][] = new int[len][len];

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    x[i][j] = 0;
                    y[i][j] = 0;
                    g[i][j] = Integer.MAX_VALUE;
                }
            }
            for (int i = 0; i < m; i++) {
                int p = sc.nextInt();
                int q = sc.nextInt();
                int k = sc.nextInt();
                int x1 = sc.nextInt();
                int y1 = sc.nextInt();
                g[p][q] = k;
                g[q][p] = k;
                x[p][q] = x1;
                x[q][p] = x1;
                y[p][q] = y1;
                y[q][p] = y1;
            }
            System.out.println(Dijkstra(g, x, y, n, 1));
        }
        sc.close();
    }

    /**
     * @param g 二维矩阵g的g[i][j]代表港i到港j的航线需要的天数；
     * @param x 二维矩阵x的x[i][j]代表港i到港j的航线不能启航的第X天；
     * @param y 二维矩阵y的y[i][j]代表港i到港j的航线不能启航的第Y天；
     * @param n 港的数量；
     * @param s 启航的港；
     * @return
     */

    private static int Dijkstra(int[][] g, int[][] x, int[][] y, int n, int s) {
        int[] dp = new int[n + 1];
        int[] vis = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[s] = 0;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            int min_p = 0;

            for (int j = 1; j <= n; j++) {
                if (dp[j] < min && vis[j] == 0) {
                    min = dp[j];
                    min_p = j;
                }
            }
            vis[min_p] = 1;

            for (int j = 1; j <= n; j++) {
                if (vis[j] != 1 && g[min_p][j] != Integer.MAX_VALUE) {
                    int temp = dp[min_p] + g[min_p][j];

                    /**
                     * 方式一
                     */
//                    if (temp < x[min_p][j]) {
//                        dp[j] = Math.min(dp[j], temp);
//                    } else {
//                        if (dp[min_p] > y[min_p][j]) {
//                            dp[j] = Math.min(dp[j], temp);
//                        } else {
//                            dp[j] = Math.min(y[min_p][j] + g[min_p][j], dp[j]);
//                        }
//                    }

                    /**
                     * 方式二
                     */
                    if (temp < x[min_p][j] || dp[min_p] > y[min_p][j])
                        dp[j] = Math.min(dp[j], temp);
                    else
                        dp[j] = Math.min(y[min_p][j] + g[min_p][j], dp[j]);

                }
            }
        }
        return dp[n] + 1;
    }
}
